An elliptic curve over a prime finite field is defined by a parameter p that is an integer that specifies a finite field Fp, over which points of the elliptic curve have their coordinates. For elliptic curves that have a parameter p of the form, p=3 mod 4 or p=5 mod 8, a square root of a number (representing a finite field element) can be easily computed by performing a single exponentiation modulo p operation. For elliptic curves such as the NIST 244 elliptic curve, the base prime number p, represented as p244, is equal to 2224−296+1. For curves of this nature, p244=1 mod 4 or 1 mod 8, and thus it is difficult to perform square root operations in a time efficient manner.
Tonelli's algorithm is a randomized algorithm that can be used for computing square roots of a number for such elliptic curves, but requires randomization to produce a single non-quadratic residue modulo p, after which it can compute multiple square roots. However, Tonelli's algorithm becomes inefficient when p−1 contains many factors of 2.
Further, the Bernstein algorithm improves on Tonelli's algorithm by using a pre-computation approach. Specifically, Bernstein maintains a table of field elements. Further reduction in computation time is obtained at the expense of a larger table. For example, by using a table that maintains 1024 elements, Bernstein achieves square root calculations with 364 multiplication operations. With a table having 3072 elements, the number of multiplication operations could be reduced to 304 and with a table of 32768 elements, the number of multiplication operations could be reduced to 258 multiplication operations.
Legendre's method finds a square root of a number q by using a quadratic extension approach. Specifically, Legendre computes the square root of a number q by computing (r2−q)(ρ+1)/2, wherein r is a randomly generated number. In order to compute the square root, it ensures that r2−q is a non-square. Legendre repeatedly chooses a uniform r until the quantity r2−q is a non-square. However, Legendre's method, like many other square root algorithms, works in a quadratic extension, where operations are more expensive than operations on the base finite field.